iT邦幫忙

2024 iThome 鐵人賽

DAY 2
0
佛心分享-刷題不只是刷題

Leecode刷題系列 第 15

D16:Q80Remove Duplicates from Sorted Array II

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20240930/201693093ijsd0g0a9.png
這題是在一個已排序的整數組 nums ,移除多餘的重複元素,讓每個元素最多出現兩次,且保持原有的順序,最後返回處理後的長度 k,要保證前 k 個元素都符合條件。

理解題目:
目標是不用額外的空間,修改輸入數組,每個數字最多只能出現兩次,且要保持元素的相對順序,返回一個整數 k,表經過修改後,符合條件的數組長度。
分析:
因為數組已排好順序,所以重複的數字一定是相鄰的,可以逐一遍歷數組,記錄每個數字的出現次數,次數大於2就跳過那個數。
技巧:
用兩個指針,一個指針 i 遍歷整個數組,另一個指針 j 追蹤有效數字位置,就是用來修改數組的內容,確認最多保留兩次(每個數字),遍歷到一個新的數或出現的次數少於等於 2 ,把那個數字放到 j 指的位置,再增加 j。
步驟:
遍歷整個 nums 數組,用變量記錄當前數字出現的次數,如果當前數字出現次數不超過兩次,就把它加到結果數組中,最後返回有效數組的長度 k。
先初始化指針,可以直接從第 2 個元素開始處理,因為前兩個元素不管怎樣都能保留,然後確認邊界條件,如果數組長度小於等於 2,那就直接返回數組長度,因為沒必要做任何操作,再遍歷數組,修改,依次查看每個元素,在需要的時後修改數組。
(用雙指針方法來解決問題)
程式碼:
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
#如果數組長度小於等於 2,直接返回數組長度,(每個元素最多出現兩次)
if len(nums) <= 2:
return len(nums)

    #j 用來指向修改後數組中的位置,從索引 2 開始
    j = 2
    
    #從索引 2 開始遍歷數組,因為要保留前兩個元素
    for i in range(2, len(nums)):
        # 如果當前元素 nums[i] 跟 nums[j-2] 不同,表可保留這個元素
        if nums[i] != nums[j-2]:
            nums[j] = nums[i]  # 把當前元素放到索引 j 的位置
            j += 1  # 更新 j 的位置
    
    return j  # 返回有效的數組長度

解釋:
初始情況,直接保留數組的前兩個元素,因為它們無論如何都是有效的,雙指針遍歷,從第三個元素開始,當前元素跟前兩個元素不同,把它保留到新的位置,結束條件,遍歷完,j 指針的值就是處理後數組的有效長度。

時間複雜度,O(n), n 是數組的長度,因為只遍歷了一次數組。
空間複雜度,O(1),因為只用了常數的額外空間。
心得:
這題考對雙指針技術的應用,這種能力對處理有序數組和數列很常見,尤其是在需要 "就地" 改數組的問題,主要是要熟悉 API ,學怎麼在不分配額外空間的情況,做數組的原地操作,對效能優化有很大的用處,一開始從簡單的問題下手,熟悉基礎概念,然後之後處理類似的高階問題會比較不會卡關,還能提升邏輯思考的能力,增強對數據結構和演算法的理解力。


上一篇
D15:Q76Minimum Window Substring
下一篇
D17:Q90Subsets II
系列文
Leecode刷題28
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言